package com.hyacinth.structure;


import com.hyacinth.utils.StringUtils;

import java.util.*;

/**
 * 字典树字符前缀模糊匹配
 * @author zhangfb
 * @version 1.0.0.1
 * @since JDK 1.8
 */
public class TrieTree {

    private static final char EMPTY_CHAR = ' ';
    private static final String EMPTY_STRING = "";

    public static void main(String[] args) {
        TrieTree t = new TrieTree();
        t.insert("中");
        t.insert("中国");
        t.insert("中国人");
        t.insert("中关村");
        t.insert("中科研究院");
        t.insert("中央党校");
        t.insert("AAAA");

        List<String> strings = t.prefixSearch("中国人");
        System.out.println(strings);
    }

    /** 根节点 */
    private Node root;

    public TrieTree() {
        this.root = new Node(EMPTY_CHAR);
    }

    /**
     * 插入数据
     * @param words 数据值(字符串)
     */
    public void insert(String words) {
        if (StringUtils.isBlank(words)) {
            return;
        }
        char[] arr = words.toCharArray();
        Node currentNode = root;
        for (char c: arr) {
            Node node = currentNode.findChildNode(c);
            //如果不存在该节点则添加
            if(node == null){
                Node n = new Node(c);
                currentNode.childList.add(n);
                currentNode = n;
            } else {
                currentNode = node;
            }
        }
        //在词的最后一个字节点标记为true
        currentNode.isEnd = true;
    }

    //判断Trie Tree中是否包含该词
    public boolean search(String word){
        char[] arr = word.toCharArray();
        Node currentNode = root;
        for (int i=0; i<arr.length; i++) {
            Node n = currentNode.findChildNode(arr[i]);
            if (n == null) {
                return false;
            }
            currentNode = n;
            //判断是否为词的尾节点
            if(n.isEnd){
                if(n.c == arr[arr.length-1]){
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 前缀匹配
     * @param words 前缀
     * @return 集合
     */
    public List<String> prefixSearch(String words) {
        List<String> res = new ArrayList<>();
        if (StringUtils.isBlank(words)) {
            return res;
        }
        return query(root, res, words, EMPTY_CHAR, EMPTY_STRING);
    }

    /**
     * @param currentNode 当前节点
     * @param res 结果集
     * @param words 前缀字符串
     * @return 结果集
     */
    private List<String> query(Node currentNode, List<String> res, String words, char wordSplit, String result) {
        // 如果当前节点是末节点，则存入结果集
        if (currentNode.isEnd && StringUtils.isBlank(words)) {
            res.add(result);
        }
        if (StringUtils.isNotBlank(words)) { // 如果单词不为空
            // 获取首位字符
            wordSplit = words.charAt(0);
            // 截取第一位
            words = words.substring(1);
            // 查询是否有该字符的子节点
            Node childNode = currentNode.findChildNode(wordSplit);
            if (childNode != null) {
                result += wordSplit;
                query(childNode, res, words, wordSplit, result);
            }
        } else {
            String tempWord = result;
            // 查询当前节点的所有子节点
            List<Node> childList = currentNode.childList;
            for (int i = 0; i < childList.size(); i++) {
                Node node = childList.get(i);
                query(node, res, words, node.c, tempWord + node.c);
            }
        }
        return res;
    }

    //最大匹配优先原则
    public Map<String, Integer> tokenizer(String words) {
        char[] arr = words.toCharArray();
        Node currentNode = root;
        Map<String, Integer> map = new HashMap<String, Integer>();
        //记录Trie Tree 从root开始匹配的所有字
        StringBuilder sb = new StringBuilder();
        //最后一次匹配到的词，最大匹配原则，可能会匹配到多个字，以最长的那个为准
        String word = "";
        //记录记录最后一次匹配坐标
        int idx = 0;
        for (int i = 0; i < arr.length; i++) {
            Node n = currentNode.findChildNode(arr[i]);
            if (n != null) {
                sb.append(n.c);
                currentNode = n;
                //匹配到词
                if (n.isEnd) {
                    //记录最后一次匹配的词
                    word = sb.toString();
                    //记录最后一次匹配坐标
                    idx = i;
                }
            } else {
                //判断word是否有值
                if(word!=null && word.length()>0){
                    Integer num = map.get(word);
                    if(num==null){
                        map.put(word, 1);
                    }else{
                        map.put(word, num+1);
                    }
                    //i回退到最后匹配的坐标
                    i=idx;
                    //从root的开始匹配
                    currentNode = root;
                    //清空匹配到的词
                    word = null;
                    //清空当前路径匹配到的所有字
                    sb = new StringBuilder();
                }
            }

            if(i==arr.length-2){
                if(word!=null && word.length()>0){
                    Integer num = map.get(word);
                    if(num==null){
                        map.put(word, 1);
                    }else{
                        map.put(word, num+1);
                    }
                }
            }
        }
        return map;
    }


    /**
     * 字典树节点
     */
    private class Node {
        //记录当前节点的字
        char c;
        //判断该字是否词语的末尾，如果是则为false
        boolean isEnd;
        //子节点
        List<Node> childList;

        public Node(char c) {
            super();
            this.c = c;
            isEnd = false;
            childList = new LinkedList<Node>();
        }

        //查找当前子节点中是否保存c的节点
        public Node findChildNode(char c) {
            for(Node node : childList) {
                if(node.c == c) {
                    return node;
                }
            }
            return null;
        }
    }
}
